class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        tmp=wordDict[:]
        wordDict={}
        for w in tmp:
            wordDict[w]=1
        res=[]
        tmp=[]
        def check(s): # 判断是不是可以拆分
            l=len(s)
            dp=[False]*(l+1)
            dp[0]=True
            for i in range(l):
                for j in range(i,-1,-1):
                    if dp[j] and s[j:i+1] in wordDict:
                        dp[i+1]=True
                        break
            return dp[l]
        def dfs(s):
            if not s:#s为空拆分到头
                res.append(tmp[:])
                return
            for word in wordDict:
                l=len(word)
                if word==s[:l]:
                    tmp.append(word)                
                    dfs(s[l:])
                    tmp.pop()# 随着递归到此处，tmp的值在递归结束时变为0
        if check(s):
            dfs(s)
        r=[]
        for e in res:
            r.append(" ".join(e))#转化形式
        return r
